__author__ = 'Brandon Corfman'
from search import SearchProblem
from path import Ladder

class FindLadderProblem(SearchProblem):
    """ Tries to find a path from the card at row,col back to the start state.
        If successful, then placing the card at row,col is valid.
    """
    def __init__(self, card, row, col, board):
        self.row, self.col = row, col
        self.card = card
        self.board = board

    def get_start_state(self):
        """
        Returns the start state for the search problem
        """
        return self.card, (self.row, self.col), 0

    def is_goal_state(self, state):
        """
        state: Search state
        Returns True if and only if the state is a valid goal state
        """
        return isinstance(state[0], Ladder)

    def get_successors(self, state):
        """
        state: Search state

        For a given state, this should return a list of triples,
        (successor, action, stepCost), where 'successor' is a
        successor to the current state, 'action' is the action
        required to get there, and 'stepCost' is the incremental
        cost of expanding to that successor
        """
        curr_row, curr_col = state[1][0], state[1][1]
        cost = state[2]
        successors = []
        for row, col in [(0,-1), (0,1), (1,0), (-1,0)]:
            new_row, new_col = curr_row + row, curr_col + col
            successor = self.board.path[new_row][new_col]
            if successor:
                successors.append((successor, (new_row, new_col), cost+1))
        return successors

class FindLeavesProblem(SearchProblem):
    """ Used with complete_depth_first_search to find the nodes (whether path cards
    or dead ends) located at the end of each tunnel found branching off from the
    start location.
    """
    def __init__(self, start_card, board):
        self.start = start_card
        self.board = board

    def get_start_state(self):
        """
        Returns the start state for the search problem
        """
        return self.start, [(self.start.row, self.start.col)], 0

    def is_goal_state(self, state):
        """
        state: Search state
        Returns True if and only if the state is a valid goal state
        """
        path = state[0]
        num_outgoing_paths = 0
        for row, col in [(0,-1), (0,1), (1,0), (-1,0)]:
            new_row, new_col = path.row + row, path.col + col
            if self.board.path[new_row][new_col] is not None:
                num_outgoing_paths += 1
        is_dead_end = path.enter != path.exit
        is_tunnel_end = num_outgoing_paths <= 1
        return is_dead_end or is_tunnel_end

    def get_successors(self, state):
        """
        state: Search state

        For a given state, this should return a list of triples,
        (successor, action, stepCost), where 'successor' is a
        successor to the current state, 'action' is the action
        required to get there, and 'stepCost' is the incremental
        cost of expanding to that successor
        """
        curr_row, curr_col = state[1][0][0], state[1][0][1]
        cost = state[2]
        successors = []
        for row, col in [(0,-1), (0,1), (1,0), (-1,0)]:
            new_row, new_col = curr_row + row, curr_col + col
            successor = self.board.path[new_row][new_col]
            if successor:
                successors.append((successor, state[1] + [(new_row, new_col)], cost+1))
        return successors